package jago02.jago0201.ag01_sort;

/**
 * 冒泡排序
 * 杂化简：多轮遍历无序数组，每次将最大值放到无序数组的末位
 * 解目录：
 *      0.将数组分为有序数组和无序数组，左边为无序数组，右边为有序数组
 *      1.初始无序数组范围为 0-n(n=数组长度-1)
 *      2.无序数组内依次比较相邻两个元素，不满足排序的相邻元素进行交换，最后将最大值交换到n位置
 *      3.n不再属于无序数组，无序数组长度上限更新为n=n-1，继续下轮比较
 * 复杂度：O(N~2)
 */
public class Sort01_Bubble {
    public static void main(String[] args) {
        Comparable[] arr = new Comparable[]{1,5,2,3,4,6,7,9};
        sort(arr);
        for (Comparable i : arr) {
            System.out.print(i+" ");
        }
    }

    private static void sort(Comparable[] arr) {
        for (int i = arr.length-1; i >0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (bigThan(arr[j],arr[j+1])){
                    exch(arr,j,j+1);
                }
            }
        }
    }

    private static void exch(Comparable[] arr, int j, int i) {
        Comparable tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    private static boolean bigThan(Comparable m, Comparable n) {
       return m.compareTo(n)>0;
    }
}
